import { Compare, defaultCompare, defaultEquals } from '../util.js'
import LinkedList from './linkedList.js'

/**
 * 有序单向链表
 */
export default class SortedLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
    super(equalsFn)
    this.compareFn = compareFn
  }

  /**
   * 重写 有序添加一个元素
   * @param {*} element 
   */
  push(element) {
    if (this.isEmpty()) {
      super.push(element)
    } else {
      const index = this.getIndexNextSortedElement(element)
      super.insert(element, index)
    }
  }

  /**
   * 重写 只在默认位置插入元素
   * @param {*} element 
   * @param {number} index 默认0
   * @returns 
   */
  insert(element, index = 0) {
    if (this.isEmpty()) {
      return super.insert(element, index === 0 ? index : 0)
    }
    const pos = this.getIndexNextSortedElement(element)
    return super.insert(element, pos)
  }

  /**
   * 获取插入元素的正确位置
   * @param {*} element 
   * @returns 
   */
  getIndexNextSortedElement(element) {
    let current = this.head
    let i = 0
    for (; i < this.size() && current; i++) {
      const comp = this.compareFn(element, current.element)
      if (comp === Compare.LESS_THAN) {
        return i
      }
      current = current.next
    }
    return i
  }
}
